package week_06;

public class MazeBollHashPathStop_1 {
    // 四个方向 前进 北 东 南 西
    int[] dx = new int[]{0, 1, 0, -1};
    int[] dy = new int[]{1, 0, -1, 0};
    boolean[][] isVisit;
    int ans;
    int m;
    int n;
    int[][] maze;
    int[] destination;

    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        m = maze.length;
        n = maze[0].length;
        isVisit = new boolean[m][n];
        this.destination = destination;
        this.maze = maze;
        find(maze, start[0], start[1], start[0], start[1]);
        return ans > 0 ? true : false;
    }

    public void find(int[][] maze, int x, int y, int i, int j) {
        // 是障碍物停止 或者是已经搜索过
        // 越界停止
        //if (isOver(x, y) || maze[x][y] == 1 || isVisit[x][y] == true) return;

        // 判断是不是答案: 四个方向 只有一个口 stop是前进的方向是 能停住的

        if (x == destination[0] && y == destination[1] && canStop(x, y, i, j)) {
            ans++;
        }
        // 四个方向尝试
        isVisit[x][y] = true;
        System.out.println("x:" + x + ":y:" + y + ":isVisit:" + isVisit[x][y] + ":maze:" + maze[x][y]);

        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (isOver(nx, ny)) continue;
            if (maze[nx][ny] == 0 && isVisit[nx][ny] == false) find(maze, nx, ny, x, y);
        }
    }

    public boolean isOver(int x, int y) {
        return x < 0 || y < 0 || x >= m || y >= n;
    }

    public boolean canStop(int x, int y, int i, int j) {
        if (x == i && y == j) return false;

        int nx = x + (x - i);
        int ny = y + (y - j);
        System.out.println(":stop:" + x + ":" + y+"->"+nx+":"+ny);
        if (isOver(nx, ny)) return true;
        if (maze[nx][ny] == 1) return true;
        return false;
    }

    public static void main(String[] args) {

        int[][] maze = new int[][]{{0, 0, 0, 0, 0}, {1, 1, 0, 0, 1}, {0, 0, 0, 0, 0}, {0, 1, 0, 0, 1}, {0, 1, 0, 0, 0}};
        int[] start = new int[]{4, 3};
        int[] destination = new int[]{0, 1};
        MazeBollHashPathStop_1 test = new MazeBollHashPathStop_1();
        test.canStop(4, 3, 4, 3);
        System.out.println(test.hasPath(maze, start, destination));
    }
}
